package com.atguigu.distributed.lock.leecode;


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 *中等230:二叉搜索树中第K小的元素
 * 二叉搜索树中第K小的元素
 */
public class KthSmallest {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(34);
        stack.push(35);
        stack.push(36);
        stack.push(37);
        stack.push(38);
        Integer pop = stack.pop();
        System.out.println("res==>"+pop);
    }
    public int kthSmallest2(TreeNode root,int k){
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            --k;
            if(k == 0){
                break;
            }
            root = root.right;
        }
        return root.data;

    }
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            root = root.right;
        }
        return root.data;
    }

}
